1. Field of the Invention
The present invention relates to a method of document layout process for generating a layout structure of a document on the basis of a logical structure of the document, and a document processing system for embodying the method.
2. Description of the Related art
Conventional document processing techniques (which will be sometimes referred to as the layout process) for generating a layout structure of a document on the basis of a logical structure of the document include, for example, an ODA technique (ISO8613: Information Processing-Text and Office Systems Open Document Architecture (ODA) and Interchange Format (1989)) and a TNT technique (J. Andere, R. Furuta, V. Quint: Structured Documents, Cambridge University Press (1989)). In these techniques, layout process is carried out on the basis of a restriction condition (which will be sometimes referred to as the `layout directive restriction`) relating to the layout of logical objects in a logical structure and a restriction condition (which will be sometimes referred to as the `structure generation restriction`) wherein a candidate for generating a layout structure is described.
The layout directive restriction is, for example, that "all structures below this logical object must be laid out in a specific frame."
The structure generation restriction is, for example, that "this page contains within the page a body frame and if necessary, a footnote frame."
The layout process must be carried out while satisfying two sorts of such layout directive and structure generation restrictions. However, there are many candidates for the generatable layout structure and whether or not the layout structure is suitable depends on the amount of contents of a logical structure to be laid out and also on the layout directive restriction. For this reason, given the document logical structure and the two sorts of restrictions, it is difficult for a processor taking a role of layout process to infer a suitable layout structure on the basis of these data.
For the purpose of overcoming this difficulty, there has been considered such a document processing system based on try and error manner that one of candidates for a layout structure is selected for layout and if the layout process ends in a failure, then the processing is returned (which will be referred to as the backtrack, hereinafter) to such a state as to allow selection of another candidate to retry the layout process and then the layout process is restarted.
Such document processing system is well known and disclosed in literatures (proceedings), for example, in 1) a paper titled "A Prototype of ODA Document Processing System (3)--Layout Process--" reported by Hayashi, Saito, Ishida and Murata in Proceedings (Sep. 12, 1988) of the 37-th General Meeting of the Information Processing Society of Japan, 2) a paper titled "A Method of Document Layout Process based on ODA (1)--Issues on Backtrack" reported by Murayama, Yamaguchi, Matsudaira, Uhehara and Kayimasa in Proceedings (Mar. 14, 1990) of the 40-th Annual Convention of the Information Processing Society of Japan, 3) a paper titled "A Method of Document Layout Process Based on ODA (2)--A Consideration of Efficiency" reported by Matsudaira, Yamaguchi and Uhehara in Proceedings (Mar. 14, 1990) of the 40-th Annual Convention of the Information Processing Society of Japan, and 4) a paper titled "A Method of Document Layout Process Based on ODA (3)--Processing Repetitive Construction" reported by Yamaguchi, Matsudaira, Uhehara and Kagimasa in Proceedings (Mar. 14, 1990) of the 40-th Annual Convention of the Information Processing Society of Japan.
In such document processing systems as disclosed in such proceeding literatures, it is considered that erroneous selection might be carried out several times in the course of generating a layout structure but a right layout structure satisfying the restriction conditions can eventually be non-manually or automatically generated.
In the above respective document processing systems, however, for the purpose of returning to such a state as to allow selection of another candidate, an alternate candidate is generated on the basis of the structure generation restriction, that is, consideration is paid only to the layout structure and no consideration is not paid at all to that position in the logical structure from which layout process is restarted. This involves a problem when re-layout process is required because a structure to be alternated is generated on the basis of the layout directive restriction.
Explanation will next be made as to a detailed example of he re-layouting problem by referring to FIGS. 9 and 13.
In FIG. 9, a part above a chain-dotted line A denotes a logical structure while a part below the line A denotes the contents of a document. In each of FIGS. 10 to 13, a part above a chain-dotted line A denotes a logical structure, a part below a chain-dotted line B denotes a layout structure, and a part sandwiched by the lines A and B therebetween denotes the contents of a document. In this connection, the logical structure and the document contents in each drawing are the same as the counterparts in FIG. 9.
In FIGS. 9 to 13, further, `logical root`, `chapter 1`, `section 1.1`, `section 1.2`, `chapter 2`, `section 2.1`, `section 2.2` and `section 2.3` represent respectively a logical object, whereas `layout root`, `page 1`, `frame 1`, `block 1--1`, `block 1-2`, `page 2`, `frame 2`, `block 2-1`, `block 2--2`, `page 2'`, `frame 2'`, `block 2'-1` and `block 2'-2` represent respectively a layout object.
Assume now that layout process is carried out as shown by a logical structure in FIG. 9. Then, since the `chapter 2` logical object has a `page change` layout directive restriction, the document processing system, when it is desired to lay out the `chapter 2` logical object, generates a new page and adds it to the layout structure.
And the document processing system performs its layout process in such a manner that the contents linked to the lower structure of the `chapter 2` logical object are laid out from its page.
Assume now that, in the course of laying out the contents of the `chapter 2`, a backtrack took place for some reason and page 2 was alternated in such a layout state as shown, for example, in FIG. 11. In this case, layout process must be restarted originally from the logical object (`chapter 2` logical object in FIG. 11) having the `page change` layout directive restriction. However, this prior art system cannot clearly find the logical object for the layout process to be restarted. For this reason, in the prior art system, the logical object linked to the contents laid out for the beginning of the page to be alternated, that is, the `section 2.1` logical object might be selected as the logical object to be restarted as shown in FIG. 12. In this case, the `page change` layout directive restriction imposed on the `chapter 2` logical object is not applied to the `section 2.1` logical object so that the leading contents of the `chapter 2` are laid out for the page (page 1) preceding the alternate candidate page (page 2) as shown in FIG. 13.
In this way, the prior art method of layout process has had such a problem that, since no consideration is taken as to the fact that the alternate candidate selection influences what layout directive restriction, it is impossible to select the alternate candidate always correctly.